//1.
/*
dfs(0,0) temp=""
└─'('→ dfs(1,0) temp="("
   ├─'('→ dfs(2,0) temp="(("
   │   └─')'→ dfs(2,1) temp="(()"
   │       └─')'→ dfs(2,2) temp="(())" ← add "(())"
   └─')'→ dfs(1,1) temp="()"
       └─'('→ dfs(2,1) temp="()("
           └─')'→ dfs(2,2) temp="()()" ← add "()()"

*/

class Solution {
public:
    vector<string> ret;
    string temp;
    void dfs(int left, int right, int n) {
        // 1. 递归出口：左右括号都凑齐了
        if (left == n && right == n) {
            ret.push_back(temp);
            return;
        }

        // 2. 分支一：还能放左括号
        if (left < n) {
            temp.push_back('(');
            dfs(left + 1, right, n);
            temp.pop_back();          // 回溯，撤销这一步选择
        }

        // 3. 分支二：还能放右括号（且不破坏合法性）
        if (right < left) {
            temp.push_back(')');
            dfs(left, right + 1, n);
            temp.pop_back();          // 回溯
        }
        return;
    }


    vector<string> generateParenthesis(int n) {
        
        dfs(0, 0, n);
        return ret;
    }
};




